# 모듈러 연산

**모듈러 연산**(Mod Arithmetic)은 정수론 핵심 개념 중로, 주어진수를 특정한(모듈러)로 나눈 나머지를 다루는 산술 체계입니다. 이 연산은 수학뿐 아니라 컴퓨터 과학, 암호학, 프로그래밍 등 다양한 분야 널리 활용되며, 특히 **시계 연산**(clock arithmetic)으로 비유되곤 합니다. 예를 들어, 12시간 시계에서 10시에 4시간을 더하면 2시가 되는 것처럼, 14를 12로 나눈 나머지가 2이므로 $ 10 + 4 \equiv 2 \pmod{12} $라고 표현합니다.

모듈러 연산은 18세기 수학자 카를 프리드리히 가우스가 《정수론 연구》(*Disquisitiones Arithmeticae*, 1801)에서 체계적으로 정립하였으며, 이후 현대 수학의 기초 도구로 자리 잡았습니다.

---

## 기본 개념

### 합동 (Congruence)

모듈러 연산의 핵심은 **합동 관계**(congruence relation)입니다. 두 정수 $ a $와 $ b $가 어떤 양의 정수 $ m $으로 나누었을 때 같은 나머지를 가지면, $ a $와 $ b $는 **모듈러 $ m $에 대해 합동**이라고 하며 다음과 같이 표기합니다:

$$
a \equiv b \pmod{m}
$$

이는 "$ a $ 빼기 $ b $는 $ m $의 배수"임을 의미하며, $ m \mid (a - b) $로도 표현할 수 있습니다.

#### 예시:
- $ 17 \equiv 5 \pmod{12} $: $ 17 - 5 = 12 $, 12는 12의 배수.
- $ 25 \equiv 1 \pmod{6} $: $ 25 \div 6 = 4 $ 나머지 1.

---

## 연산 법칙

모듈러 연산은 덧셈, 뺄셈, 곱셈, 거듭제곱 등에서 다음과 같은 성질을 가집니다.

### 기본 연산의 보존성

임의의 정수 $ a, b, c, d $와 모듈러 $ m $에 대해,  
만약 $ a \equiv b \pmod{m} $이고 $ c \equiv d \pmod{m} $이면:

- **덧셈**: $ a + c \equiv b + d \pmod{m} $
- **뺄셈**: $ a - c \equiv b - d \pmod{m} $
- **곱셈**: $ a \cdot c \equiv b \cdot d \pmod{m} $
- **거듭제곱**: $ a^n \equiv b^n \pmod{m} $ (단, $ n $은 자연수)

이러한 성질은 모듈러 연산이 대수적 구조(특히 **환**(ring))를 형성함을 보여줍니다.

---

## 활용 예시

### 1. 시계 연산 (시간 계산)

24시간제에서 현재 시간이 21시(오후 9시)일 때, 8시간 후의 시간은 다음과 같이 계산됩니다:

$$
21 + 8 = 29 \equiv 5 \pmod{24}
$$

즉, 8시간 후는 다음 날 오전 5시입니다.

---

### 2. 암호학에서의 활용

모듈러 연산은 **공개키 암호**(예: RSA)의 기초입니다. RSA 알고리즘은 큰 소수와 모듈러 거듭제곱, 모듈러 역수를 기반으로 하며, 다음 과정에서 사용됩니다:

- 두 큰 소수 $ p, q $를 곱하여 $ n = p \cdot q $ 생성.
- 오일러의 파이 함수 $ \phi(n) = (p-1)(q-1) $ 계산.
- $ e $와 $ d $를 선택하여 $ e \cdot d \equiv 1 \pmod{\phi(n)} $가 되도록 함.
- 암호화: $ c \equiv m^e \pmod{n} $
- 복호화: $ m \equiv c^d \pmod{n} $

이러한 방식은 모듈러 연산의 **역산의 어려움**(특히 이산 로그 문제)에 보안을 기반합니다.

---

### 3. 프로그래밍에서의 사용

프로그래밍 언어에서는 `%` 연산자를 통해 모듈러 연산을 구현합니다.

```python
a = 17 % 5  # 결과: 2
b = (10 + 8) % 12  # 결과: 6
```

이는 배열 인덱스 순환(예: 원형 큐), 해시 함수 설계, 난수 생성 등에 활용됩니다.

---

## 모듈러 역수와 페르마의 소정리

### 모듈러 역수 (Modular Inverse)

정수 $ a $와 $ m $이 서로소일 때, 다음을 만족하는 $ x $를 **모듈러 역수**라고 합니다:

$$
a \cdot x \equiv 1 \pmod{m}
$$

이를 $ x \equiv a^{-1} \pmod{m} $로 표기합니다.

예: $ 3 \cdot 7 = 21 \equiv 1 \pmod{10} $이므로, $ 3^{-1} \equiv 7 \pmod{10} $.

모듈러 역수는 **확장 유클리드 알고리즘** 또는 **페르마의 소정리**를 통해 계산할 수 있습니다.

---

### 페르마의 소정리 (Fermat's Little Theorem)

$ p $가 소수이고 $ a $가 $ p $로 나누어지지 않으면:

$$
a^{p-1} \equiv 1 \pmod{p}
$$

따라서 $ a $의 모듈러 역수는 다음과 같이 구할 수 있습니다:

$$
a^{-1} \equiv a^{p-2} \pmod{p}
$$

이는 RSA 및 디피-헬만 키 교환 등에서 효율적인 계산에 활용됩니다.

---

## 관련 개념

- **잉여류**(Residue Class): 모듈러 $ m $에 대해 같은 나머지를 갖는 정수들의 집합. 예: $ \overline{2} $는 2와 모듈러 5에서 합동인 모든 정수.
- **완전잉여계**(Complete Residue System): 모듈러 $ m $에 대해 서로 다른 나머지를 갖는 $ m $개의 정수 집합. 보통 $ \{0, 1, 2, ..., m-1\} $ 사용.
- **기약잉여계**(Reduced Residue System): 모듈러 $ m $과 서로소인 나머지들의 집합. 크기는 $ \phi(m) $.

---

## 참고 자료 및 관련 문서

- 가우스, *Disquisitiones Arithmeticae* (1801)
- Rosen, Kenneth H. *Elementary Number Theory and Its Applications*
- [Wikipedia: Modular Arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic)
- 관련 위키 문서: [[정수론]], [[소수 (수론)]], [[암호학]], [[RSA 암호]]

모듈러 연산은 단순한 나머지 계산을 넘어서, 현대 수학과 정보 기술의 기반이 되는 강력한 도구입니다. 깊이 있는 이해는 수학적 사고력과 알고리즘 설계 능력을 향상시키는 데 기여합니다.